package practice_once_time;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Activity{
    public int start;
    public int finsh;
    public Activity(int start,int finsh){
        this.start=start;
        this.finsh=finsh;
    }
}
public class ActivitySelection {

    public static List<Activity> SelectionActivity(Activity[] activities){
        //收容活动集合
        List<Activity> selectActivity=new ArrayList<>();
        //排序，使activities数组里的元素按从小到大排序
        Arrays.sort(activities,new Comparator<Activity>(){
            public int compare(Activity a1,Activity a2){
                return Integer.compare(a1.finsh,a2.finsh);
            }
        });
        
        selectActivity.add(activities[0]);//将排序好的第一个活动加入收容集合
        int previousFinshTime=activities[0].finsh;//第一个活动的结束时间作第一次的参考时间
        //贪心算法选择活动，从第二个活动开始
        for (int i=1;i< activities.length;i++){
            Activity currentActivity =activities[i];//记录当前活动
            //如果当前活动的开始时间晚于前一个活动的结束世家
            if (currentActivity.start>= previousFinshTime){
                selectActivity.add(currentActivity);//收容该活动
                previousFinshTime= currentActivity.finsh;//更新结束时间

            //如果当前活动的开始时间提前于前一个活动的结束时间，并且当前活动的结束时间也提前于前一个活动的结束时间
            }else if (currentActivity.finsh<previousFinshTime){
                selectActivity.remove(selectActivity.size()-1);//移除当前集合的收容活动
                selectActivity.add(currentActivity);//加入当前最优解
                previousFinshTime=currentActivity.finsh;
            }
        }
        return selectActivity;
    }

    public static void main(String[] args){
        Activity[] activities={new Activity(0,4),
                new Activity(0,2),
                new Activity(2,4),
                new Activity(4,7),
                new Activity(4,6),
                new Activity(6,10),
                new Activity(6,8),
                new Activity(10,13),
                new Activity(8,13),
                new Activity(8,10)
        };

        List<Activity> activityList=SelectionActivity(activities);
        System.out.println("收容的最大活动集合为：");

        for (Activity activity:activityList){
            System.out.println("("+activity.start+","+activity.finsh+")");
        }

    }
}
